KDD 2021 | 基于多智能体协同竞价博弈的电商搜索广告多目标竞价优化

▐  导读

本文提出了一套多目标协同出价优化框架，即多智能体协同出价博弈（以下简称：MACG）。在该合作博弈框架中，通过引入一个全局目标以优化所有广告主的总体利益，鼓励广告主更好的协同，从而间接保护自主出价广告主的利益，使得流量分配更加公平。通过理论分析给出了最优出价公式的泛函形式，并设计了一种策略网络用于探索泛函出价公式中的最优参数。为寻找最优参数，我们设计了一种高效的多智能体进化策略搜索算法。目前该方案已在淘宝搜索广告平台上进行离线评测和在线A/B测试，效果显著。该项工作论文已发表在 KDD 2021，欢迎交流讨论。

论文链接：https://arxiv.org/abs/2106.04075

▐  1. 背景

在线广告是互联网流量变现的重要方式，即以互联网为媒体，广告主在互联网平台发布相应的广告信息，平台设置相应的竞价机制，将流量分发到对应的广告主，满足广告主的营销目的，同时平台获取相应的广告费用收入。电商在线广告竞价市场主要有三部分组成，广告主，消费者和平台。广告主端规模超百万，营销诉求多样；消费者端日请求数十亿，需求各有不同；平台的目标在于通过满足广告主需求以及平衡消费者体验，获得更高的营收。

在竞价过程中，广告主倾向于以更低的成本获得最大的收益，平台则设计分配和扣费的市场机制。但因流量本身高度动态，所以广告主之间会各自独立报价，这个过程难以实现个体理性的报价。这种非合作博弈的均衡状态往往无法实现整体效益的最大化，作为平台在保障平台利益前提下，如何推动广告主之间有限的协作，实现集体理性的报价，成为更大挑战。

图1.1淘宝app根据用户请求返回的结果（标红为广告）

如图1.1所示，当用户输入“连衣裙”请求，返回相应的商品列表，通常排在第一位的是广告主投放的广告，其他为非广告位，当用户向下滑动到一页，则再次请求平台引擎进行重新竞价，相应的第一位为广告位。由于淘宝电商平台的搜索广告，广告即商品，只是每页第一资源位为广告，第一资源位对应的点击率和成交率也明显高于同页的其他资源位。广告主会通过合理出价竞争相应的广告资源位，以求获得更大收益。

学术界和工业界已经深入研究了单广告主视角的竞价优化问题，这些研究往往即假设其他竞争者不改变出价，这一强假设往往不成立，导致策略在运用于多广告主真实竞价时表现差强人意。少量现有工作从多广告主视角，利用多智能体强化学习，通过构建一致的目标进行出价的协同优化，但大多存在如下缺陷：

（1）由于信息完全共享，这些方法很难避免多广告主串谋的问题，一种显而易见的更优解是广告主串通出较低价竞价流量，导致平台收益受损；

（2）在复杂动态的竞价环境中，这些策略需要较长时间收敛并且极度不稳定。此外，针对电商搜索广告竞价优化问题，以往的工作很少考虑同时优化广告主多样化的诉求目标。

针对以上问题，本文提出了一套多目标协同出价优化框架，即多智能体协同出价博弈。在该合作博弈框架中，通过引入一个全局的目标以优化所有广告主的总体利益，鼓励了广告主更好的协同，从而间接保护了自主出价广告主的利益，使得流量分配更加公平。为解决多广告主串谋问题，额外引入平台收入作为约束。通过理论分析给出了最优出价公式的泛函形式，并设计了一种策略网络用于探索泛函出价公式中的最优参数。为寻找最优参数，同时设计了一种高效的多智能体进化策略搜索算法。该模型已经上线部署到淘宝搜索广告平台，每天服务上百万广告主的实时竞价优化，使得整体大盘效率指标以及广告主自身诉求均有 5% 以上提升。

▐  2．问题定义

本章将该多诉求目标广告主竞价问题进行严谨的数学定义。我们将全天作为一个回合（episodic）的竞价过程，将回合内所有竞价 定义为竞价集合 。将所有利用智能出价广告（AD）  定义为集合 , 将利用自主出价的广告 i\  定义为集合 。 和 分别表示一个广告和一次竞价。同时不同广告可以根据不同的诉求目标聚簇为不同的广告集合，其数学表示为： 且 。同时，记AD 对竞价 的出价为。对于每次竞价 ，所有出价的AD 均按照eCPM排序，其中。是预估的点击率，同时将不关注如何预估点击率，作为出价优化直接的输入量。本文定义一个指示变量 如下：

(3-1)

刻画AD 是否竞得竞价 。对于工业系统广泛采用的广义第二高价（GSP），即按照下一名的出价扣费。定义表示扣费，定义如下：

(3- 2)

, 分别表示下一名的点击率和出价。从，的定义中，可以看出都与出价相关，表示如下：

(3- 3)

对于属于第  类诉求 AD  的目标函数表示如下：

(3- 4)

表示属于第 类诉求 AD 的集合。表示对应的诉求。除了AD自身目标，本文也引入了额外的总体目标，定义如下：

(3- 5)

其中， 。对于约束方面，每个AD有自己的预算约束B和单位成本约束C（如果没有，约束B和单位成本约束C则为无穷大）。此外引入了平台每千次展现收益（RPM）为约束去避免广告主互相串谋，记为 ，其物理意义相当于投入产出比的倒数，则即为累积的RPM消耗。为了鼓励智能出价的广告主，本文引入了较低的下界对于，计作自主出价。对于每一个AD，智能出价策略应该不低于自主出价策略。至此，本文给出完整的数学定义如下：

（3-6）

这里需要指出，集合 是受集合决定的，后者仅局部决定了平台收益，即只影响智能出价部分。同时每次竞价，只有一个竞得者。

▐  3．理论分析

基于上述公式的问题定义，我们发现有两种类型的目标，全局的目标 和广告主自身的目标集合 。由于 ，均受 影响，且多广告主共同竞价时，对于广告主将成为变量，直接将上述公式转为对偶问题将难以推导和求解。这两种目标均受RPM和分配变量约束，这两种约束就分配变量而言是线性的。因此将上述问题，拆成两个子问题，一是求解基于总体目标下的出价，另一个是求解基于广告主自身的目标出价。我们先对两个子问题进行定义，子问题1定义如下:

（3-7）

子问题2定义如下:

（3-8）

子问题1和子问题2均对原始问题转为对偶问题进行求解，同时该问题建模为线性规划经历了一次松弛，将原始的整数规划问题转化成了线性规划问题，即：

(3- 9)

该操作增大了解空间。以子问题2为示例，进行相应的理论推导，同时泛化到子问题1。

据此构造出价策略为：

(3- 10)

当不存在单位成本约束时，

(3- 11)

至此，基于对偶问题推导出了针对子问题2的最优出价形式。对于子问题1给出最优出价公式：

(3- 12)

即按照成交诉求参照公式（3-11）计算的实时出价。所有AD均按照\alpha_j\ast GMV_{ij}进行排序，基于此出价能够保证优化总体的GMV目标。从原始问题定义，是将总体优化目标和广告主自身多诉求优化目标同时求解。相应的，设计理论上的最优出价公式为：

（3-13）

其中为需要学习的权重参数。我们认为上述的出价包含了针对原始的问题帕累托解集。

从上述公式（3-11）可以得出，从理论上设计的最优出价公式，包括两部分：一部分是广告主自身基于诉求目标进行的出价；另一部分是针对总体优化目标进行的报价。如果直接利用线性规划求解，对于百万量级的广告主，数千亿次的竞价数据，该求解规模是线性规划求解完全不能承受的。对于该难点，我们拟采用网络化近似求解广告主出价部分和针对总体出价部分的参数。对于上述公式中，将两部分直接将广告主出价部分和针对总体目标出价部分线性融合，为了更好的融入实时的特征信息，分配的权重可以以网络化更精准的求解。

▐  4．模型求解

整个模型框架如图4.1所示，不同诉求的广告主首先按照诉求目标进行聚簇形成个聚簇集合。对于每次竞价 ，每类诉求的 AD 首先利用自身的实时特征 作为自身私有网络的输入，计算针对 AD 自身诉求的 作为输出。同时利用竞价 下所有AD的实时特征 和分布特征 作为共享网络的输入，计算针对总体目标的出价 作为输出。此外利用分布特征 作为融合网络的输入，计算针对私有网络和共享网络的分配权值 作为输出。此时得到任意一个AD 在每次竞价 下的最终出价 。此时对于同一竞价下，按照 eCPM 进行排序，Top AD 获得展现，对全天每次竞价进行如上计算和排序，通过累计全天的不同诉求的广告主和总体的目标分数，根据多目标设计和进化策略优化更形模型参数，从而探索最初的出价参数。

图4. 1多智能体协同进化策略模型总体框架

4.1 私有网络

基于理论最优公式，我们首先针对客户目标的出价部分进行网络求参。对AD自身私有的网络抽象为 ，表示属于第 类诉求的AD 在竞价 下，输入实时状态 计算自身出价 。其出价函数如下：

(4-1)

参考最优出价公式， 表征基于 AD 自身目标的出价， 表示属于第k\ 类诉求的在竞价 下的目标。为了更好的刻画第 类诉求AD 对竞价 相关性，我们设计了 函数，以实时的状态信息 作为输入，利用神经网络进行计算。同时为了缩小解空间，我们将其神经网络的输出通过 sigmoid 函数映射到 [-range, range] 范围内，range 为超参。

既兼顾了理论分析最优出价公式中的AD部分，又更好的以神经网络利用状态的实时特征求解参数，从而更好的优化AD自身诉求目标。

4.2 共享网络

基于问题定义中，通过引入总体目标来促进广告主之间更好的合作，减少无效的竞争。同时引入总体约束，防止广告主共同出低价作弊。在上述理论上的最优出价中，当以总体GMV为目标时， 成为实现总体目标的出价部分。AD共享网络抽象为 ，表示在竞价 下，输入实时状态 和分布特征 计算针对总体目标的出价 。其出价函数如下：

(4-2)

其中的 等于 ，是通过计算AD之前历史数据计算出来的。 表示广告的平均抽成率，即每份收入对应的消耗占比。引入 旨在衡量竞价 下整体的竞价能力。此外，为了利用实时的状态信息刻画竞价 下所有AD的降价环境，设计了 函数，以竞价下分布特征 为输入，通过多层神经网络的计算，利用sigmoid函数映射到 [-range, range] 范围内。

4.3 融合网络

通过上述的私有网络和共享网络分别针对广告主自身目标和总体目标计算了实时出价 和 ，如何更好的将基于两者目标的出价融合，设计了融合网络抽象为 ，以竞价下分布特征 为输入，通过多层神经网络的计算，通过 sigmoid 映射到（0，1）之间，用来实时分配私有网络和共享网络的权重。

则AD 对竞价 最终的出价公式如下：

(4-3)

4.5 多目标设计

本文主要考虑广告主三种主流的目标：

目标1：单位成本（CPC）约束下最大化点击（CTR）；

目标2：预算（w）约束下最大化成交额（GMV）；

目标3：预算（w）约束下最大话加购收藏（CART）。

总体目标为预算（w）约束下最大化成交额（GMV）。首先定义一个累积函数如下：

(4-5)

其中， 表示AD 是否赢得竞价 的分配变量， 表示目标诉求，V 表示要累积的目标量， 表示 属于竞价 下属于第 类诉求的 AD 集合。比如预算累积量则表示为：，其中 表示AD 对竞价 的扣费。

为了更好的优化多目标，我们设计将多目标分数进行归一化。通过另一种基准策略将竞得竞价分配变量 ，我们采用OCPC作为此基准策略。此时，目标分数中两种策略的约束比例作为惩罚项，优化目标的比例作为奖励项。则，对于目标1，定义目标分数 如下：

(4-6)

其中， 表示累积的消耗除以累积的点击量，表示单位成本约束， 表示累积的点击量。

此外，定义总体的目标 如下：

(4-7)

其中， 表示消耗持平的情况下，绝对值表征只有当0时约束惩罚项最小。为了约束项相一致，对优化项同时减1操作。

至此，本文完整定义了三类广告主目标分数以及总体的目标分数，接下来将基于这四个目标分数，设计相应的进化策略求解最优出价的网络参数。

4.6 进化策略优化

本小节将详细介绍如何利用 和 通过进化策略进行多目标优化。考虑到大规模的竞价数据，即使在离线模拟，对计算资源的消耗也非常庞大，因此，设计更轻量级的进化优化策略更加有必要性。首先对于广告主多样化诉求，设计如下优化目标：

(4-8)

即每次迭代中，仅选取目标分数值最小的目标进行优化，不仅减少超参量，而且更易于广告主多目标的可拓展性。对于融合广告主自身目标和总体目标，直接利用加权融合引入超参 ，则将多目标专为单目标优化 定义如下：

(4-9)

接下来，通过 利用进化策略进行模型参数更新。首先对三个策略网络随机初始化10万组参数，利用离线模拟器进行仿真，对每组参数通过累积全天的 和 ，对于这10万组参数，选择 最高的2000组参数作为种子，通过对这2000组参数，基于正态分布进行随机扰动产生10万组新的参数，重复上述的模拟，在新一轮选择参数时，为了更好的保证模型的收敛性，要求选择 和 都大于上一轮选择种子中对应的分数中 最高的 2000 组参数。如此更新迭代，直至 和 收敛。

▐  5．实验结果

5.1 淘宝数据集及离线模拟器

本文收集了4天淘宝搜索广告离线的日志数据（July 15th, 2020, July 16th, 2020, August 8th, 2020 and August 9th, 2020) 。本节中分别将 July 15th, 2020 和 August 8th, 2020 作为训练数据，相应的 July 16th, 2020 和 August 9th, 2020 做对对应的测试数据。对于训练和测试数据中，分别统计不同诉求目标AD的占比，GMV诉求，CART诉求和 click诉求分别占比 52%，11% 和 38%。

5.2 离线实验

表5.1呈现了不同对比方法的实验结果。MACG 明显优于表格中所有对比方法在各个指标上， 和 指标的提升也验证了多目标协同优化对于同时提升多目标设计思路的优越性，同时 和 指标的提升也验证了进化学习在避开强化学习时间片状态转移建模思路，基于参数空间扰动采用天级别优化上的优势。

5.3 收敛性分析

图5.1 August 8,2020 和 July 15,2020训练迭代中的收敛情况

广告主多诉求目标优化问题是通过进化策略进行优化，模型相对于对比实验和消融实验部分都验证了该模型的有效性，但对于进化策略如何在迭代过程中影响多个目标协同优化的过程，也同样有必要进行相关分析。如图5.1所示，展示了 MACG 在不同天训练迭代的收敛情况。可以看出在前五轮不同指标的震荡性比较大，从第10轮迭代左右，不同指标开始呈现一定的稳定性，在20轮左右，基本已经开始收敛。对于百万量级的广告主，数百亿次竞价数据在20轮左右就呈现较强的收敛性，证明了该模型较强的拟合能力和优化能力。

对此我们进行了如下分析：1）本文三个网络按照超参中的设置，总共的神经网络参数为5*（8*4+4）=180，其中三组私有网络参数，一组共享网络参数，一组融合网络参数，对于小于200的神经网络参数，进化学习更容易快速拟合；2）进化学习是通过累积全天的目标分数来进行选择，而不是如强化学习在时间片上利用经验池来迭代以及训练Q网络来预估未来的收益训练，所以相对于强化学习，更加容易收敛和更具有稳定性。

5.4 在线实验

图 6.2 连续 15 天在线实验结果(2020.9.12-2020.9.26)

如图6.2展示了连续15天的在线实验结果，可观测到如下结论：

1）MACG 在各个指标线上均提升5%以上。相对于线上基准桶的静态出价策略OCPC，多智能体协同进化策略一方面能够对动态的环境实时建模，利用实时特征做个性化的实时报价，更精准的刻画了当下的竞争环境；另一方面是协同优化所有广告主，相较与 OCPC 对各自的目标的优化，能够更好的探索最优解。利用共享出价网络和实时分配网络来优化总体目标，从而让总体目标与广告主自身目标在博弈的过程中更好的优化两者效果。

2）MACG 呈现了相对的稳定性在连续15天里（如 和 标准差分别是 0.84%，0.75%，0.34%，0.91%）。这证明了 MACG 模型在线实验的有效性和稳定性。进化策略不用对未来的收益做预估（相较于强化学习），利用历史数据探索全局最优解，从而对于线上波动的数据分布，也能够更好的拟合动态的竞价过程。

▐  总结

本文针对大规模电商实时竞价场景，提出了更准确的多目标竞价优化问题的数学定义及理论分析。基于先验出价公式的形式，对模型设计提供了合理的理论依据且缩小探索空间；提出了多智能体协同竞价优化模型。基于理论上带参的先验出价公式，设计了利用神经网路和进化学习来近似求解的出价策略，根据最优公式，设计三网络联合出价，利用多智能体协同进化策略更新网络参数寻找最优出价。目前该方案已在淘宝电商平台全量上线，为上百万的广告主提供竞价服务；同时，也为多目标竞价优化问题，提供了更加高效和鲁棒性的解决方案。

未来我们将进一步研究轻量级的多目标优化算法，尝试新的进化学习策略，更好的协同多目标之间的博弈。

参考文献

[1] Jin J, Song C, Li H, et al. Real-time bidding with multi-agent reinforcement learning in display advertising[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 2018: 2193-2201.

[2] Zhao J, Qiu G, Guan Z, et al. Deep reinforcement learning for sponsored search real-time bidding[C]//Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 2018: 1021-1030.

[3] Zhang W, Yuan S, Wang J. Optimal real-time bidding for display advertising[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014: 1077-1086.

关于我们

我们是阿里妈妈广告主赋能算法团队，服务于百万量级广告主效果优化，欢迎感兴趣的同学加入我们~

简历投递邮箱：[e-mail]

END

欢迎关注「阿里妈妈技术」，了解更多~

疯狂暗示↓↓↓↓↓↓↓